#ifndef SOLUTION_H_
#define SOLUTION_H_
#include <vector>
#include <algorithm>

using namespace std;

class Solution{
public:
	int threeSumClosest(vector<int>& num,int target){
		int lastIndex[3] = {-1,0,0};
		int lastClosest = 0;

		sort(num.begin(),num.end());
		size_t nNum = num.size();
		for(size_t i=0;i < (nNum-2);i++){
			size_t h = i+1, t = nNum-1;

			while(h<t){
				int sum = num[i]+num[h]+num[t];
				if((-1 == lastIndex[0]) || (abs(sum-target) < abs(lastClosest-target))){
					lastClosest = sum;
					lastIndex[0] = i;
					lastIndex[1] = h;
					lastIndex[2] = t;
					if(sum == target)
						break;
				}
				if(sum > target){
					t--;
				}
				else
					h++;
			}			
		}
		return lastClosest;
	}
};
#endif